package algorithm.manacher;

public class Manacher {
    //求最长回文子串的长度
    //如果当前位置在R（讲述中的R，最右的扩成功的位置）的右侧，则暴力的方法，需要一个一个向外扩
    //如果当前的位置在R左侧，1、如果范围卡在了R上，则有可能需要进一步扩展
    //                     2、如果范围在R内或者超出了R，则该点的回文半径已定

    //从左向右遍历字符串，求每个位置的最长回文半径，更新R和C以加速对后面位置回文半径的求解。
    public static int manacher(String s){
        if(s == null || s.length() == 0)
            return 0;
        char[] chars = manacherString(s);
        //R代表最右的扩成功的位置的下一个位置
        int R = -1;
        //与R相匹配的中心点
        int C = -1;
        // 回文半径的大小
        int[] pArr = new int[chars.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < chars.length; i++) {
            pArr[i] = i >= R ? 1 : Math.min(pArr[2 * C - i], R - i);
            while(i + pArr[i] < chars.length && i - pArr[i] >= 0){
                if(chars[i + pArr[i]] == chars[i - pArr[i]])
                    pArr[i]++;
                else
                    break;
            }
            if(i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
                max = Math.max(max, pArr[i]);
            }

        }
        return max - 1;
    }

    public static char[] manacherString(String s){
        char[] chars = s.toCharArray();
        char[] result = new char[chars.length * 2 + 1];
        int j = 0;
        for (int i = 0; i < chars.length; i++, j++) {
            result[j] = '#';
            result[++j] = chars[i];
        }
        result[j] = '#';
        return result;
    }


    public static void main(String[] args) {
//        System.out.println(new String(manacherString("abcd")));
        int i = manacher("abcba");
        System.out.println(i);
    }
}
